package com.alex.算法.动态规划;

/**
 * 目标：在背包容量限制下，选择若干物品（每个物品只能选或不选），使得总价值最大。
 * 输入：
 * 物品数量 n，背包容量 W。
 * 每个物品的重量 w[i] 和价值 v[i]（1 ≤ i ≤ n）。
 * 输出：能装入背包的最大总价值。
 */
public class 背包问题 {

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        System.out.println("最大价值: " + knapsack(weights, values, capacity)); // 输出 10
    }

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];

        // 外层循环遍历每个物品。
        for (int i = 0; i < n; i++) {
            // 内层循环逆序遍历背包容量，确保每个物品只被选择一次。
            // 必须逆序遍历，防止重复选择同一物品
            for (int j = capacity; j >= weights[i]; j--) {
                //
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }
}
